// 2025/3/5
// https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
// 缺失的第一个正数

// 利用原数组进行哈希的两种方法

// 置换
class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int n = nums.size();
            for(int i = 0; i < n; i++)
            {
                while(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
                    swap(nums[i], nums[nums[i] - 1]);
            }
    
            for(int i = 0; i < n; i++)
            {
                if(nums[i] != i + 1)
                    return i + 1;
            }
    
            return n + 1;
        }
    };

// 标记
class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int n = nums.size();
            for (int& num: nums) {
                if (num <= 0) {
                    num = n + 1;
                }
            }
            for (int i = 0; i < n; ++i) {
                int num = abs(nums[i]);
                if (num <= n) {
                    nums[num - 1] = -abs(nums[num - 1]);
                }
            }
            for (int i = 0; i < n; ++i) {
                if (nums[i] > 0) {
                    return i + 1;
                }
            }
            return n + 1;
        }
    };